package demo.practice.dp;

//https://alchemist-al.com/algorithms/wildcard-matching 动态规划画图表
public class P5_2 {


    public static void main(String[] args) {
        P5_2 p5_2 = new P5_2();
        p5_2.longestPalindrome("cbbd");
    }

    public String longestPalindrome(String s) {
        int len = s.length();
        boolean dp[][] = new boolean[len][len];

        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        int maxlen = 1;
        int fl = 0;
        char[] cs = s.toCharArray();
        for (int i = 1; i < s.length(); i++) {
            for (int j = i-1; j >=0; j--) {
                if (cs[i] != cs[j]) {
                    dp[i][j] = false;
                } else {
                    dp[i][j] = i - 1 <= j + 1 || dp[i - 1][j + 1];
                    if (dp[i][j]&&maxlen < i - j + 1) {
                        maxlen = i - j + 1;
                        fl = j;
                    }
                }
            }
        }
        return s.substring(fl, fl+maxlen);
    }
}
